#region License

// This file is part of Grawlix.
// 
// Grawlix is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as
// published by the Free Software Foundation, either version 3 of
// the License, or (at your option) any later version.
// Grawlix is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public
// License along with Grawlix.  If not, see
// <http://www.gnu.org/licenses/>.

#endregion

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using C5;

namespace Grawlix.Geometry
{
	/// <summary>
	/// A closed, convex 2D shape without curved edges.
	/// </summary>
	[SuppressMessage("Microsoft.Design", "CA1001",
		Justification = "Disposable fields do not need disposal.")
	]
	public class ConvexPolygon : Shape
	{
		/// <summary>
		/// The area of the shape.
		/// </summary>
		private readonly float _area;

		/// <summary>
		/// The center point of the shape.
		/// </summary>
		private readonly Vector2 _centroid;

		/// <summary>
		/// The list of normals of each edge.
		/// </summary>
		private readonly C5.IList<Vector2> _normalList;

		/// <summary>
		/// The center point of the shape.
		/// </summary>
		private readonly OrientedRect _orientedBoundingBox;

		/// <summary>
		/// The list of vertices determining the shape.
		/// </summary>
		private readonly ArrayList<Vector2> _vertexList;

		/// <summary>
		/// Initializes a polygon from a set of vertices.
		/// </summary>
		/// <param name="vertexCollection">The set of vertices use.
		/// Must be convex and specified in counter-clockwise order.
		/// Use <see cref="ConvexHull"/> if data source is unsure.
		/// </param>
		/// <exception cref="ArgumentNullException">
		/// <paramref name="vertexCollection"/> is null</exception>
		/// <exception cref="InvalidGeometryException">
		/// <paramref name="vertexCollection"/> is not a strict convex
		/// polygon, specified in counter-clockwise order.
		/// </exception>
		public ConvexPolygon(IEnumerable<Vector2> vertexCollection)
		{
			if (vertexCollection == null)
				throw new ArgumentNullException("vertexCollection");

			_vertexList = new ArrayList<Vector2>();
			_vertexList.AddAll(vertexCollection);

			// Polygons must have 3 or more verticies.
			int count = _vertexList.Count;
			if (count < 3)
			{
				throw new InvalidGeometryException(
					"A polygon must have at least three vertices. " +
					"Only " + count + " were specified.");
			}

			_normalList = ComputeNormals();
			EnsureConvexAndCounterClockwise();

			// Figure out the centroid and bounding box of the polygon.
			CentroidResult centroidResult = ComputeCentroid();
			_centroid = centroidResult.ResultingCentroid;
			_area = centroidResult.ResultingArea;
			_orientedBoundingBox = ComputeOrientedBoundingBox();
		}

		/// <summary>
		/// The area of the polygon.
		/// </summary>
		public override float Area
		{
			get { return _area; }
		}

		/// <summary>
		/// The centroid of the shape.
		/// </summary>
		/// <remarks>The centroid of a shape is its center of mass,
		/// given uniform density.</remarks>
		public override Vector2 Centroid
		{
			get { return _centroid; }
		}

		/// <summary>
		/// Read-only access to the normals of each edge.
		/// </summary>
		public C5.IList<Vector2> Normals
		{
			get { return new GuardedList<Vector2>(_normalList); }
		}

		/// <summary>
		/// The minimal oriented bounding box enclosing the shape.
		/// </summary>
		public override OrientedRect OrientedBoundingBox
		{
			get { return _orientedBoundingBox; }
		}

		/// <summary>
		/// Read-only access to the vertices comprising the polygon.
		/// </summary>
		public C5.IList<Vector2> Vertices
		{
			get { return new GuardedList<Vector2>(_vertexList); }
		}

		/// <summary>
		/// Compute the centroid of a polygon.
		/// </summary>
		/// <returns>The centroid of the polygon.</returns>
		/// <seealso cref="ConvexHull"/>
		private CentroidResult ComputeCentroid()
		{
			var centroid = new Vector2(0, 0);
			float area = 0;
			Vector2 previousVertex = _vertexList.Last;
			foreach (var currentVertex in _vertexList)
			{
				float triangleArea =
					previousVertex.ExteriorMultiply(currentVertex);

				area += triangleArea;
				centroid += (previousVertex + currentVertex) *
				            triangleArea;

				previousVertex = currentVertex;
			}
			Debug.Assert(area > float.Epsilon);
			centroid /= (area * 3);
			area /= 2;
			return new CentroidResult(centroid, area);
		}

		/// <summary>
		/// Compute the normals of the given list of convex polygon
		/// vertices.
		/// </summary>
		/// <returns>A new 
		/// <see cref="ArrayList{T}"/>
		/// storing the normals of the polygon.</returns>
		/// <exception cref="InvalidGeometryException">
		/// The vertices provided do not specify a valid strict convex
		/// polygon in counter-clockwise order. Or, there are duplicate
		/// vertices.
		/// </exception>
		private ArrayList<Vector2> ComputeNormals()
		{
			int count = _vertexList.Count;
			var normalList = new ArrayList<Vector2>(count);
			Vector2 previousVertex = _vertexList.Last;
			foreach (var currentVertex in _vertexList)
			{
				Vector2 edge = currentVertex - previousVertex;
				// Checks for NaN
				if (!(edge.InnerMultiply(edge) > float.Epsilon))
				{
					throw new InvalidGeometryException(
						"Polygon edges must have nonzero length. " +
						"The edge between " + previousVertex + " and " +
						currentVertex + " does not.");
				}
				Vector2 normal =
					new Vector2(edge.Y, -edge.X).Normalize();
				normalList.Add(normal);

				previousVertex = currentVertex;
			}

			return normalList;
		}

		/// <summary>
		/// Find the Minimum-Area Rectangle Containing a Convex
		/// Polygon.
		/// </summary>
		/// <returns>The <see cref="OrientedRect"/> with minimum area,
		/// containing the polygon.</returns>
		/// <remarks>
		/// <para>
		/// <c>Elby</c>, David. Minimum-Area Rectangle Containing a
		/// Convex Polygon. June 2, 2000.
		/// http://www.geometrictools.com/Documentation/MinimumAreaRectangle.pdf
		/// </para>
		/// <para>
		/// From the Box2D adaptation by Erin <c>Catto</c>.
		/// </para>
		/// </remarks>
		/// <seealso cref="ConvexHull"/>
		private OrientedRect ComputeOrientedBoundingBox()
		{
			var orientedBoundingBox = new OrientedRect();

			float minimumArea = float.MaxValue;
			Vector2 root = _vertexList.Last;
			foreach (var currentVertex in _vertexList)
			{
				Rotation2 rotation = (currentVertex - root).Rotation;
				var transform = new Transform2(root, rotation);
				float left = float.MaxValue;
				float right = float.MinValue;
				float height = float.MinValue;
				foreach (var d in _vertexList)
				{
					Vector2 r = transform.ApplyInverse(d);
					left = Math.Min(left, r.X);
					right = Math.Max(right, r.X);
					height = Math.Max(height, r.Y);
				}
				float width = right - left;
				Debug.Assert(height > float.Epsilon);
				Debug.Assert(width > float.Epsilon);
				float area = width * height;
				if (area < minimumArea)
				{
					minimumArea = area;
					var center = new Vector2(left + width / 2, height / 2);
					center = transform.Apply(center);
					var dimensions = new Vector2(width, height);
					orientedBoundingBox = new OrientedRect(center,
					                                       dimensions,
					                                       rotation);
				}
				root = currentVertex;
			}

			Debug.Assert(minimumArea < float.MaxValue);
			return orientedBoundingBox;
		}

		/// <summary>
		/// Checks to see if a point is within the
		/// current <see cref="Shape"/>.
		/// </summary>
		/// <param name="point">The point to check.</param>
		/// <returns>true if within, else false.</returns>
		public override bool Contains(Vector2 point)
		{
			for (int i = 0; i < _vertexList.Count; ++i)
			{
				float dot =
					_normalList[i].InnerMultiply(point - _vertexList[i]);
				if (dot > 0f)
					return false;
			}

			return true;
		}

		/// <summary>
		/// Computes the convex hull of points in a plane.
		/// </summary>
		/// <param name="points">Any set of points.</param>
		/// <returns>A list of points, in counter-clockwise order,
		/// determining the minimum convex shape to enclose all the
		/// points, starting with the leftmost, then lowest point.
		/// </returns>
		/// <remarks>
		/// <para>
		///	Graham's Algorithm for finding the convex hull in a plane,
		///	as modified by Andrew.
		/// </para>
		/// <para>
		/// As implemented in:
		/// <c>Kokholm</c>, Niels and<c>Sestoft</c>. The C5 Generic
		/// Collection Library for C# and CLI. 2006. 200-201.
		/// http://www.itu.dk/research/c5/
		/// </para>
		/// </remarks>
		/// <exception cref="ArgumentNullException">
		/// <paramref name="points"/> is null</exception>
		public static C5.IList<Vector2> ConvexHull(
			IEnumerable<Vector2> points)
		{
			if (points == null)
				throw new ArgumentNullException("points");

			var pointList = new ArrayList<Vector2>();
			pointList.AddAll(points);
			if (pointList.Count == 0)
				return pointList;

			// 1. Sort points lexographically by increasing (x, y)
			pointList.Sort(new LexicographicVector2Comparer());
			Vector2 left = pointList[0];
			Vector2 right = pointList[pointList.Count - 1];
			if (left == right)
				return pointList.View(0, 1);

			// 2. Partition into lower hull and upper hull
			var upper = new C5.LinkedList<Vector2>();
			var lower = new C5.LinkedList<Vector2>();
			lower.InsertFirst(left);
			upper.InsertLast(left);
			foreach (var point in pointList)
			{
				// Signed polygonal area, with origin at left
				float det = (right - left).ExteriorMultiply(point - left);
				if (det < 0)
					lower.InsertFirst(point);
				else if (det > 0)
					upper.InsertLast(point);
			}
			lower.InsertFirst(right);
			upper.InsertLast(right);

			// 3. Eliminate points not on the hull.
			Eliminate(lower);
			Eliminate(upper);

			// 4. Join the lower and upper hull, leaving out
			// lower.First and upper.First
			lower.RemoveFirst();
			upper.RemoveFirst();
			var result =
				new ArrayList<Vector2>(lower.Count + upper.Count);
			result.AddAll(lower.Backwards());
			result.AddAll(upper.Backwards());
			return result;
		}

		/// <summary>
		/// Graham's point elimination scan.
		/// </summary>
		/// <param name="list">A list of sorted <see cref="Vector2"/>
		/// structures.</param>
		/// <seealso cref="ConvexHull"/>
		private static void Eliminate(C5.IList<Vector2> list)
		{
			C5.IList<Vector2> view = list.View(0, 0);
			int slide = 0;
			while (view.TrySlide(slide, 3))
			{
				Vector2 v1 = view[1] - view[0];
				Vector2 v2 = view[2] - view[0];
				// Signed polygonal area, with origin at view[0]
				if (v1.ExteriorMultiply(v2) < 0) // right turn
					slide = 1;
				else
				{
					// left or straight
					view.RemoveAt(1);
					slide = view.Offset != 0 ? -1 : 0;
				}
			}
		}

		///<summary>
		/// Ensures that a polygon is convex and in counter-clockwise
		/// order.
		///</summary>
		///<exception cref="InvalidGeometryException">
		/// The polygon is not convex or specified in counter-clockwise
		/// order.
		/// </exception>
		private void EnsureConvexAndCounterClockwise()
		{
			// Ensure convex and counter-clockwise.
			int count = _normalList.Count;
			for (int i = 0; i < count; ++i)
			{
				Vector2 currentNormal = _normalList[i];
				Vector2 nextNormal = _normalList[(i + 1) % count];

				float product =
					currentNormal.ExteriorMultiply(nextNormal);
				if (product > float.Epsilon)
					continue;
				throw new InvalidGeometryException(
					"A ConvexPolygon was specified " +
					"either not strictly concave or in clockwise order. " +
					"One of these two problems has occurred, as two " +
					"adjacent edges were specified with the three points: " +
					_vertexList[(i + count - 1) % count] + ", " +
					_vertexList[i] + " and " + _vertexList[(i + 1) % count] +
					".");
			}
		}

		/// <summary>
		/// Checks if the polygon is too thin or its angles are too
		/// narrow.
		/// </summary>
		/// <param name="minimumLinearSlope">The minimum distance
		/// between each edge and vertex not on the edge.</param>
		/// <param name="minimumAngularSlope">The minimum internal
		/// angle.
		/// </param>
		/// <returns>true if valid, else false.</returns>
		public bool IsValid(float minimumLinearSlope,
		                    float minimumAngularSlope)
		{
			int count = _vertexList.Count;

			for (int i = 0; i < count; ++i)
			{
				// Check to see that the distance between
				// the line through each edge is at least the
				// minimum away from each vertex not on the edge.
				Vector2 normal = _normalList[(i + 1) % count];
				Vector2 edgeVertex = _vertexList[i];
				for (int j = (i + 2) % count;
				     j != i;
				     j = (j + 1) % count)
				{
					Vector2 current = _vertexList[j];
					float distance =
						normal.InnerMultiply(edgeVertex - current);
					if (!(distance >= minimumLinearSlope))
						return false;
				}

				// Check that the interior angle between each edge is 
				// greater than the minimum.
				float cosine = _normalList[i].InnerMultiply(normal);
				cosine = Math.Min(Math.Max(cosine, -1), 1);
				var angle = (float)Math.Acos(-cosine);
				if (!(angle >= minimumAngularSlope))
					return false;
			}
			return true;
		}

		/// <summary>
		/// Obtains a string representation of this object.
		/// </summary>
		/// <returns>A string representation of this object.</returns>
		public override string ToString()
		{
			return _vertexList.ToString();
		}

		///<summary>
		/// The resulting centroid and area.
		///</summary>
		private struct CentroidResult
		{
			/// <summary>
			/// The area result.
			/// </summary>
			private readonly float _resultingArea;

			/// <summary>
			/// The centroid result.
			/// </summary>
			private readonly Vector2 _resultingCentroid;

			///<summary>
			///Initializes the results of computing the centroid.
			///</summary>
			///<param name="centroid">The centroid result.</param>
			///<param name="area">The area result.</param>
			public CentroidResult(Vector2 centroid, float area)
			{
				_resultingCentroid = centroid;
				_resultingArea = area;
			}

			/// <summary>
			/// The area result.
			/// </summary>
			public float ResultingArea
			{
				get { return _resultingArea; }
			}

			/// <summary>
			/// The centroid result.
			/// </summary>
			public Vector2 ResultingCentroid
			{
				get { return _resultingCentroid; }
			}
		}
	}
}